package com.leetcode.graph;

/**
 * @author Dennis Li
 * @date 2020/9/9 15:42
 */
public class LongestIncreasingPath_329 {

    public static void main(String[] args) {
        int[][] res = {{9,9,4},{6,6,8},{2,1,1}};

        LongestIncreasingPath_329 ans = new LongestIncreasingPath_329();

        int path = ans.longestIncreasingPath(res);

        System.out.println(path);
    }

    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    int[][] memo;

    public int longestIncreasingPath(int[][] matrix) {
        int len = matrix.length;
        memo = new int[len][len];
        int max = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (memo[i][j] == 0)
                    max = Math.max(max, dfs(matrix, i, j));
            }
        }
        return max;
    }

    private int dfs(int[][] matrix, int i, int j) {
        if (memo[i][j] != 0) {
            return memo[i][j];
        }
        memo[i][j]++;
        for (int[] d : directions) {
            int y = i + d[0], x = j + d[1];
            if (y >= 0 && y < matrix.length && x >= 0 && x < matrix[0].length
                    && matrix[y][x] > matrix[i][j]) {
                // 求从这个点延伸出去的最长的长度
                // +1：子节点长度 + 1（当前结点）
                memo[i][j] = Math.max(memo[i][j], dfs(matrix, y, x) + 1);
            }
        }
        return memo[i][j];
    }

}
